# @Time    : 2020/6/19 20:59
# @Author  : T-
# @Site    : 
# @File    : 24-Swap Nodes in Pairs.py
# @Software: PyCharm

from utils import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # method-1:递归法
        # 从head开始，设置firstNode和secondNone两个结点，最后返回secondNode（新头）
        # 交换后的头是原始链表的第二个节点
        # 若无节点或只有一个节点
        if not head or not head.next:
            return head

        first_node = head
        second_node = head.next

        first_node.next =  self.swapPairs(second_node.next)
        second_node.next = first_node

        return second_node

        # method-2:迭代法
        # 链表分奇数和偶数节点
        # prev_node为前节点的前驱节点
        dummy = ListNode(-1)
        dummy.next = head

        prev_node = dummy

        while head and head.next:
            first_node = head
            second_node = head.next

            # 交换的前驱节点
            prev_node.next = second_node

            # 执行交换
            first_node.next = second_node.next
            second_node.next = first_node

            # 移动prev_node和head
            prev_node = first_node
            head = first_node.next

        return dummy.next


        # method-2.1:迭代法优化
        dummy = ListNode(-1)
        dummy.next = head

        if not head or not head.next:
            return head

        prev_node = head        # 奇数
        aft_node = head.next    # 偶数

        while aft_node and aft_node.next:
            first_node = aft_node
            second_node = aft_node.next

            prev_node.next = second_node

            # 交换
            first_node.next = second_node.next
            second_node.next = first_node

            prev_node = first_node
            aft_node = first_node.next

        return dummy.next




















